public class Solution {
    public static int lastStoneWeightII(int[] s) {
        int n = s.length;
        int sum = 0;
        for(int x : s){
            sum += x;
        }
        int m = sum / 2;
        int[] dp = new int[m + 1];
        for(int i = 1; i <= n; i++){
            for(int j = m; j >= s[i-1]; j--){
                if(j >= s[i-1]){
                    dp[j] = Math.max(dp[j], dp[j-s[i-1]] + s[i-1]);
                }
            }
        }
        int ret = 0;
        for(int i = 0; i <= m; i++){
            ret = Math.max(ret, dp[i]);
        }
        return sum - 2 * ret;

    }

    public static void main(String[] args) {
        int[] s = {2,7,4,1,8,1};
        System.out.println(lastStoneWeightII(s));

    }
}
